package LeetCode._02算法基础.day01二分查找;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 10 - 19:51
 * @Description 编写一个高效的算法来搜索m x n矩阵 matrix 中的一个目标值 target
 * 该矩阵具有以下特性：
 * 每行的元素从左到右升序排列
 * 每列的元素从上到下升序排列
 * @Version 1.0
 */
public class _74搜索二维矩阵 {
    static int[][] matrix = {
            {1,4,7,11,15},
            {2,5,8,12,19},
            {3,6,9,16,22},
            {10,13,14,17,24},
            {18,21,23,26,30}
    };
    static int target = 5;
    @Test
    public void solve(){
        boolean res = searchMatrix(matrix, target);
        System.out.println(res);
    }
    /* by me 每行二分查找 O(n*log n) */
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int i = 0; i < matrix.length; i++){
            if(binarySearch(matrix[i], target)){
                return true;
            }
        }
        return false;
    }
    public boolean binarySearch(int[] array, int target){
        int left = 0, right = array.length - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(array[mid] == target){
                return true;
            }else if(array[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
    /* 类二分查找 */
    //矩阵右上角的元素左边的比它小，右边的比它大
    public boolean searchMatrix1(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] < target){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }
}
